package com.zjsru.plan2024.oneday;

import java.util.*;

/**
 * 1436. 旅行终点站
 *
 * @Author: cookLee
 * @Date: 2024-10-08
 */
public class DestCity {

    /**
     * 主
     * \
     * 输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
     * 输出："Sao Paulo"
     * 解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。
     * \
     * 输入：paths = [["B","C"],["D","B"],["C","A"]]
     * 输出："A"
     * 解释：所有可能的线路是：
     * "D" -> "B" -> "C" -> "A".
     * "B" -> "C" -> "A".
     * "C" -> "A".
     * "A".
     * 显然，旅行终点站是 "A" 。
     * \
     * 输入：paths = [["A","Z"]]
     * 输出："Z"
     * \
     * @param args args
     */
    public static void main(String[] args) {
        DestCity destCity = new DestCity();
        List<String> path1 = Arrays.asList("London", "New York");
        List<String> path2 = Arrays.asList("New York", "Lima");
        List<String> path3 = Arrays.asList("Lima", "Sao Paulo");
        List<List<String>> paths = new ArrayList<>();
        paths.add(path1);
        paths.add(path2);
        paths.add(path3);
        System.out.println(destCity.destCity(paths));
    }

    /**
     * 目地城市:哈希表
     *
     * @param paths 路径
     * @return {@link String}
     */
    public String destCity(List<List<String>> paths) {
        Map<String, Integer> pathMap = new HashMap<>();
        for (List<String> path : paths) {
            String start = path.get(0);
            String end = path.get(1);
            pathMap.put(start, pathMap.getOrDefault(start, 0) - 1);
            pathMap.put(end, pathMap.getOrDefault(end, 0) + 1);
        }
        return pathMap.entrySet().stream().filter(v -> pathMap.get(v.getKey()) > 0).findFirst().get().getKey();
    }

    /**
     * 目地城市2：哈希表
     *
     * @param paths 路径
     * @return {@link String}
     */
    public String destCity2(List<List<String>> paths) {
        Map<String, String> map = new HashMap<>();
        for (List<String> path : paths) {
            map.put(path.get(0), path.get(1));
        }
        //终点城市不存在key值
        String ptr = paths.get(0).get(0);
        while (map.containsKey(ptr)) {
            ptr = map.get(ptr);
        }
        return ptr;
    }

}
